import java.util.ArrayList;
import java.util.Arrays;

public class Leetcode {
}
//leetcode:300:最长递增子序列
class Solution1 {
    public int lengthOfLIS(int[] nums) {
        ArrayList<Integer> ret = new ArrayList<>();
        int n = nums.length;
        ret.add(nums[0]);

        for(int i = 1; i < n; i++){
            //判断当前的数是否大于最后一个数，如果大于就将他放入其中
            if (nums[i] > ret.get(ret.size() - 1)) {
                ret.add(nums[i]);
            } else {
                //如果不大于，就进行二分查找，更新最接近这个数的位置元素的值
                int left = 0 , right = ret.size() - 1;
                while(left < right){
                    int mid = (left + right) / 2;
                    if(nums[i] > ret.get(mid)) left = mid + 1;
                    else right = mid;
                }
                ret.set(left , nums[i]);
            }
        }
        return ret.size();
    }
}

//leetcode:334:递增的三元子序列
class Solution2 {
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        if(n < 3) return false;

        int first = nums[0] , secound = Integer.MAX_VALUE;
        for(int i = 1; i < n; i++){
            //如果这个数大于第二个数，那么就代表存在递增的三元子序列
            if(nums[i] > secound) return true;
                //如果大于第一个数，但不大于第二个数，就更新第二个数的值
            else if (nums[i] > first) secound = nums[i];
                //如果小于第一个数就更新第一个数的值
            else first = nums[i];
        }
        return false;
    }
}

//leetcode:1005:k次取反后最大化的数组和
class Solution3 {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int sum = 0 , n = nums.length;
        //排序
        Arrays.sort(nums);
        for(int i = 0; i < n; i++){
            //将在k次允许范围内的负数变为正数
            if(nums[i] < 0 &&  k > 0){
                nums[i] = nums[i] * -1;
                k--;
            }
            sum += nums[i];
        }
        //重新排序
        Arrays.sort(nums);
        //如k剩余的次数是2的倍数，无论如何取反最大值都是此时的和
        //如果不为2的倍数，就让他对最小值即nums[0]进行取反即可，此时的最大值就是sum - 2*nums[0]，因为我们是在本来的数上进行取反所以要减两次
        return k % 2 == 0 ? sum : sum - 2*nums[0];
    }
}